package com.fwpsl.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author: 风戏fw
 * @date: 2024/3/30
 * @description: 非比较排序： 计数排序、桶排序、基数排序
 */
public class NonCompareSort {

    /**
     * 计数排序
     *
     * @param arr
     */
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 找到数组中的最大值和最小值
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }

        // 初始化计数数组，长度为最大值-最小值+1
        int[] countArr = new int[max - min + 1];
        // 统计每个数字出现的次数
        for (int num : arr) {
            countArr[num - min]++;
        }

        int i = 0, j = 0;
        while (i < countArr.length) {
            while (i < countArr.length && countArr[i] == 0) {
                i++;
            }

            if (i >= countArr.length) {
                break;
            }

            while (countArr[i] > 0) {
                arr[j++] = i + min;
                countArr[i]--;
            }
        }
    }

    /**
     * 桶排序
     *
     * @param arr
     */
    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 找到数组中的最大值和最小值
        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        // 计算桶的数量
        int bucketCount = (int) Math.floor((maxValue - minValue) / arr.length) + 1;

        // 初始化桶
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将数据放入桶中， 按范围平分桶
        for (int value : arr) {
            int bucketIndex = (int) Math.floor((value - minValue) * (bucketCount - 1) / (maxValue - minValue));
            buckets.get(bucketIndex).add(value);
        }

        // 对每个桶中的数据进行排序
        for (int i = 0; i < bucketCount; i++) {
            if (!buckets.get(i).isEmpty()) {
                Collections.sort(buckets.get(i));
            }
        }

        // 合并桶中的数据
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int value : bucket) {
                arr[index++] = value;
            }
        }
    }

    /**
     * 基数排序
     *
     * @param arr
     */
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 找到数组中最大数的位数
        int max = findMax(arr);
        int digitCount = countDigits(max);

        // 创建一个桶数组，大小为10，因为每一位数字的范围是0-9
        int[][] buckets = new int[10][arr.length];
        int[] bucketCounts = new int[10];
        // 对每一位进行排序
        for (int i = 0; i < digitCount; i++) {
            // 遍历数组，根据当前位的数字将元素放入桶中
            for (int j = 0; j < arr.length; j++) {
                int digit = getDigit(arr[j], i);
                buckets[digit][bucketCounts[digit]] = arr[j];
                bucketCounts[digit]++;
            }

            // 从桶中取出元素，放回原数组
            int index = 0;
            for (int k = 0; k < 10; k++) {
                for (int l = 0; l < bucketCounts[k]; l++) {
                    arr[index++] = buckets[k][l];
                }
                // 重置桶计数
                bucketCounts[k] = 0;
            }
        }
    }

    // 辅助方法：找到数组中的最大值
    private static int findMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    // 辅助方法：计算数字的位数
    private static int countDigits(int num) {
        int count = 0;
        while (num > 0) {
            num /= 10;
            count++;
        }
        return count;
    }

    // 辅助方法：获取数字的第n位（从右边开始计数，从0开始）
    private static int getDigit(int num, int n) {
        int digit = (num / (int) Math.pow(10, n)) % 10;
        return digit;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{15, 38, 84, 11, 3, 38, 91, 13, 65, 49, 43};
        System.out.println("before sort:" + Arrays.toString(arr));

//        countingSort(arr);
//        bucketSort(arr);
        radixSort(arr);

        System.out.println("after sort:" + Arrays.toString(arr));
    }
}
